#! /bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #! /bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create:
#   README
#   glib.c
#   graphtypes.h
#   input.form
#   main.c
#   makefile
#   match.defs
#   output.form
#   pairs.c
#   pointer.c
#   readgraph.c
#   term.c
#   test.in
#   unpairs.c
#   wmatch.c
# This archive created: Thu Feb 21 19:32:51 EST 1991
export PATH; PATH=/bin:/usr/bin:/usr/ucb:/usr/bin:/etc:/usr/etc:/usr/local/X11R4/bin:/usr/local/bin:/dimacs/u2/badics/bin:/dimacs/u2/badics/out:/usr/lib/news:.
if test -f 'README'
then
	echo shar: "will not over-write existing file 'README'"
else
cat << \SHAR_EOF > 'README'
-------------------------------------------------------------------
The Match_C.shell file contains a program, written in C, for finding 
MAXIMUM-WEIGHT MATCHING for UNDIRECTED graphs.  
-------------------------------------------------------------------

This program was written by Ed Rothberg to implement H. Gabow's N-cubed 
weighted matching algorithm, as described in his Ph.D. thesis 
"Implementation of Algorithms for Maximum Matching on Nonbipartite Graphs" 
Stanford University, 1973.  


MAIN PROGRAMS:
		- wmatch

REQUIRED FILES:
		README input.form output.form makefile graphtypes.h glib.c pairs.c
		term.c pointer.c readgraph.c unpairs.c match.defs wmatch.c main.c

TO GET THESE FILES:
        Run the "Match_C.shell" file in the /bin/sh shell. 
		(It will unwrap itself.)

FILE DESCRIPTIONS: 
		input.form:  Describes the input formats for match.
		output.form: Describes output formats for match.
						***Format converters will be available soon to
						translate input and output files from and to the
						DIMACS Challenge format. Contributions are welcome. 
		
		test.in:  A sample input for wmatch
		
        The others are source code files written in C language.

HOW TO MAKE THE PROBLEM-SOLVERS:

		wmatch:  Solves maximum matching for undirected graphs presented in an 
		       adjacency-list format. 

		       Requires:graphtypes.h glib.c pairs.c term.c pointer.c 
						readgraph.c unpairs.c match.defs wmatch.c main.c makefile 
 
		
		       To compile: $make
		       To invoke: $wmatch input_file
		
		      If no filename is given, a small help message appears. It always  
		      writes to standard out.  

/ This README file was written by DIMACS, and based on experiments with the
codes. /


SHAR_EOF
fi
if test -f 'glib.c'
then
	echo shar: "will not over-write existing file 'glib.c'"
else
cat << \SHAR_EOF > 'glib.c'
#include "graphtypes.h"
#include <stdio.h>
#include <math.h>

AddEdge (g,n,m,label)
Graph g;
int n,m,label;

{	Edge edge1,edge2;

	edge1 = (Edge) malloc(2*sizeof(struct edge_ent));
	edge2 = edge1 + 1;

	edge1->label = label;
	edge1->endpoint = m;
	edge1->otheredge = edge2;
	edge1->prevedge = NULL;
	edge1->nextedge = g[n].adj_list;
	if (edge1->nextedge != NULL)
		edge1->nextedge->prevedge = edge1;
	g[n].adj_list = edge1;
	g[n].degree++;

	edge2->label = label;
	edge2->endpoint = n;
	edge2->otheredge = edge1;
	edge2->prevedge = NULL;
	edge2->nextedge = g[m].adj_list;
	if (edge2->nextedge != NULL)
		edge2->nextedge->prevedge = edge2;
	g[m].adj_list = edge2;
	g[m].degree++;
}

Edge FindEdge(graph,i,j)
Graph graph;
int i,j;

{	Edge edge;

	edge = graph[i].adj_list;
	while (edge!=NULL && edge->endpoint!=j)
		edge = edge->nextedge;
	if (edge==NULL) return(NULL);
	else return(edge);
}

int RemoveEdge(graph,edge)
Graph graph;
Edge edge;

{	Edge other;
	int i,j;

	if (edge==NULL) return(0);
	other = edge->otheredge;
	i = other->endpoint;
	j = edge->endpoint;
	graph[i].degree--; graph[j].degree--;
	if (edge->prevedge == NULL) {
		graph[i].adj_list = edge->nextedge;
		if (edge->nextedge != NULL)
			edge->nextedge->prevedge = NULL;
		}
	else if (edge->nextedge == NULL)
        	(edge->prevedge)->nextedge = NULL;
	else {
		(edge->nextedge)->prevedge = edge->prevedge;
		(edge->prevedge)->nextedge = edge->nextedge;
		}
	if (other->prevedge == NULL) {
		graph[j].adj_list = other->nextedge;
		if (other->nextedge != NULL)
			other->nextedge->prevedge = NULL;
		}
	else if (other->nextedge == NULL)
		(other->prevedge)->nextedge = NULL;
	else {
		(other->nextedge)->prevedge = other->prevedge;
		(other->prevedge)->nextedge = other->nextedge;
		}
	free((edge < other) ? edge : other);
	return(1);
}

int NumEdges(g)
Graph g;
{	int i,size,edges;

	edges = 0;
	size = Degree(g,0);
	for (i=1; i<=size; i++)
		edges += Degree(g,i);
	edges /= 2;
	return(edges);
}

Graph NewGraph(size)
int size;
{	Graph tmp;
	int i;

	tmp = (Graph) malloc((size+1)*sizeof(struct node_entry));
	for (i=1; i<=size; i++) {
		Degree(tmp,i) = 0;
		FirstEdge(tmp,i) = NULL;
		NLabel(tmp,i) = i;
		}
	Degree(tmp,0) = size;
	return(tmp);
}

EuclidGraph NewEuclid(size)
int size;
{
	EuclidGraph xy;

	xy = (EuclidGraph) malloc((size+1)*2*sizeof(int));
	xy[0][0] = size;
	return(xy);
}

MatrixGraph NewMatrix(size)
int size;
{
	MatrixGraph graph;
	int i;

	graph = (MatrixGraph) malloc((size*(size+1)+1)*sizeof(int));
	graph[0] = size;

	for (i=1; i<=size; i++)		/* zero the diagonal */
		graph[i*(size+1)] = 0;

	return(graph);
}

Graph CopyGraph(g)
Graph g;
{	int i,j,size;
	Edge edge;
	Graph cp;

	size = Degree(g,0);
	cp = NewGraph(size);
	for (i=1; i<=size; i++) {
		Xcoord(cp,i) = Xcoord(g,i);
		Ycoord(cp,i) = Ycoord(g,i);
		edge = FirstEdge(g,i);
		for (j=1; j<=Degree(g,i); j++) {
			if (i < EndPoint(edge))
				AddEdge(cp,i,EndPoint(edge),ELabel(edge));
			edge = NextEdge(edge);
			}
		}
	return (cp);
}

/* Graph I/O routines */

Graph ReadGraph (size,file)
int *size;
char file[];

{	Graph graph;
	FILE *fp;
 	char c;
	int edges, degree, vlabel, elabel, adj_node, i, j;
	int xcoord, ycoord;

	if (file[0] == '\0') fp = stdin;
	else fp = fopen(file,"r");
	if (fp==NULL) {
		printf("ReadGraph: file %s can't be opened\n",file);
		exit(0);
		}
	fscanf(fp,"%d%d %c",size,&edges,&c);
	if (c !='U' && c!='u') {
		printf("ReadGraph: file %s does not contain an undirected graph\n",file);
		exit(0);
		}
	while (getc(fp)!='\n') ;

	graph = NewGraph(*size);
	for (i = 1; i <= *size; ++i) {
		fscanf(fp,"%d%d%d%d",&degree,&vlabel,&xcoord,&ycoord);
		NLabel(graph,i) = vlabel;
		Xcoord(graph,i) = xcoord;
		Ycoord(graph,i) = ycoord;
		while (getc(fp)!='\n') ;
		for (j = 1; j <= degree; ++j) {
			fscanf(fp,"%d%d", &adj_node, &elabel);
			while (getc(fp)!='\n') ;
			if (i<adj_node)
				AddEdge (graph,i,adj_node,elabel);
			}
		}
	fclose(fp);
	return(graph);
}

WriteGraph (graph,file)
Graph graph;
char file[];

{	FILE *fp;
	int size, i,j,edges;
	Edge p;

	if (file[0] == '\0') fp = stdout;
	else fp = fopen(file,"w");
	if (fp==NULL) {
		printf("WriteGraph: file %s can't be opened\n",file);
		exit(0);
		}
	size = Degree(graph,0);
	edges = NumEdges(graph);
	fprintf(fp,"%d %d U\n",size,edges);

	for (i = 1; i <= size; i++) {
		fprintf(fp,"%d %d %d %d L\n",Degree(graph,i),NLabel(graph,i),
					   Xcoord(graph,i),Ycoord(graph,i));
		p = FirstEdge(graph,i);
		for (j = 1; j <= Degree(graph,i); ++j) {
			fprintf(fp,"%d %d L\n",EndPoint(p),ELabel(p));
			p = NextEdge(p);
			}
		}
	fclose(fp);
}

EuclidGraph ReadEuclid(size,file)
int *size;
char file[];

{	EuclidGraph graph;
	FILE *fp;
	char c;
	int i,xcoord, ycoord;

	if (file[0]=='\0') fp=stdin;
	else fp = fopen(file,"r");
	if (fp==NULL) {
		printf("ReadEuclid: file %s can't be opened\n",file);
		exit(0);
		}
	fscanf(fp,"%d %c",size,&c);
	if (c!='E' && c!='e') {
		printf("ReadEuclid: file %s isn't Euclidean\n",file);
		exit(0);
		}
	while (getc(fp)!='\n');
	graph = NewEuclid(*size);

	for (i=1; i<=*size; ++i) {
		fscanf(fp,"%d%d",&xcoord,&ycoord);
		while (getc(fp)!='\n') ;
		graph[i][0] = xcoord;
		graph[i][1] = ycoord;
		}
	fclose(fp);
	return (graph);
}

WriteEuclid(graph,file)
EuclidGraph graph;
char file[];

{	FILE *fp;
	int size, i;

	if (file[0] == '\0') fp = stdout;
	else fp = fopen(file,"w");
	if (fp==NULL) {
		printf("WriteEuclid: file %s can't be opened\n",file);
		exit(0);
		}
	size = graph[0][0];
	fprintf(fp,"%d E\n",size);
	for (i = 1; i <= size; i++) 
		fprintf(fp,"%d %d\n",graph[i][0],graph[i][1]);
	fclose(fp);
}

MatrixGraph ReadMatrix(size,file)
int *size;
char file[];
{	MatrixGraph graph;
	FILE *fp;
	char c;
	int i,j,k;

	if (file[0]=='\0') fp=stdin;
	else fp = fopen(file,"r");
	if (fp==NULL) {
		printf("ReadMatrix: file %s can't be opened\n",file);
		exit(0);
		}
	fscanf(fp,"%d %c",size,&c);
	if (c!='M' && c!='m') {
		printf("ReadMatrix: file %s isn't a distance matrix\n",file);
		exit(0);
		}
	while (getc(fp)!='\n');
	graph = NewMatrix(*size);

	for (i=1; i<*size; i++) {
		for (j=i+1; j<=*size; j++) {
			fscanf(fp,"%d",&k);
			graph[i*(*size)+j] = graph[j*(*size)+i] = k;
			}
		while (getc(fp)!='\n');
		}
	fclose(fp);
	return(graph);
}

WriteMatrix(graph,file)
MatrixGraph graph;
char file[];

{	FILE *fp;
	int size, i, j;

	if (file[0] == '\0') fp = stdout;
	else fp = fopen(file,"w");
	if (fp==NULL) {
		printf("WriteMatrix: file %s can't be opened\n",file);
		exit(0);
		}
	size = graph[0];
	fprintf(fp,"%d M\n",size);
	for (i = 1; i < size; i++) {
		for (j=i+1; j<=size; j++)
			fprintf(fp,"%d ",graph[i*size+j]);
		fprintf(fp,"\n");
		}
	fclose(fp);
}

/* Euclidean distance routines */

int eucdist (graph,i,j) /* Find the distance between two points */
			/* 10K x 10K unit square */
EuclidGraph graph;
int i,j;
{	int dv,dh;
	register int k, l;

	dv = graph[i][0]-graph[j][0];
	dh = graph[i][1]-graph[j][1];
	k = dv*dv + dh*dh;
	if (k==0) return(0);
	if (dv<0) dv = -dv;
	if (dh<0) dh = -dh;
	l = dv + dh;
	l = (l + k/l)>>1;
	l = (l + k/l)>>1;
	l = (l + k/l)>>1;
	l = (l + k/l)>>1;
	return ((l*l<k) ? ++l : l);
}


int eucdist2 (graph,i,j) /* Find the distance between two points */
			/* 1M x 1M unit square */
EuclidGraph graph;
int i,j;
{	double dv,dh,d;
	int l;

	dv = (double) graph[i][0]-graph[j][0];
	dh = (double) graph[i][1]-graph[j][1];
	d  = sqrt(dv*dv + dh*dh);
	l  = (int) d;
	return((d-l > .000000001) ? l+1 : l);
}


int eucdistsq(graph,i,j) /* Find the square of the dist between two points */
EuclidGraph graph;
int i,j;
{
	register int dv,dh;

	dv = graph[i][0]-graph[j][0];
	dh = graph[i][1]-graph[j][1];
	return(dv*dv+dh*dh);
}

SHAR_EOF
fi
if test -f 'graphtypes.h'
then
	echo shar: "will not over-write existing file 'graphtypes.h'"
else
cat << \SHAR_EOF > 'graphtypes.h'
#define INF	100000000
#define NULL	0

struct node_entry {
    int degree;
    int label;
    int x;
    int y;
    struct edge_ent *adj_list;
    };
typedef struct node_entry *Graph;

struct edge_ent {
    int endpoint;
    int label;
    int label2;
    struct edge_ent *nextedge;
    struct edge_ent *prevedge;
    struct edge_ent *otheredge;
    };
typedef struct edge_ent *Edge;

extern Graph ReadGraph(),NewGraph(),CopyGraph();
extern int RemoveEdge(),NumEdges();
extern Edge FindEdge();

#define Degree(graph,n)    (graph[n].degree)
#define NLabel(graph,n)    (graph[n].label)
#define Xcoord(graph,n)    (graph[n].x)
#define Ycoord(graph,n)    (graph[n].y)
#define FirstEdge(graph,n) (graph[n].adj_list)

#define EndPoint(e) (e->endpoint)
#define ELabel(e)   (e->label)
#define ELabel2(e)  (e->label2)
#define Other(e)    (e->otheredge)
#define NextEdge(e) (e->nextedge)


extern Graph Prim();
extern int *EulerTraverse(),*Match(),*Weighted_Match(),*Dijkstra(),*Concomp();

/* Euclidean graph type */
typedef int (*EuclidGraph)[2];

extern Graph EuclidPrim();
extern EuclidGraph ReadEuclid(),NewEuclid();
extern int eucdist(),eucdistsq();

extern int *CvxHull();

/* Distance matrix graph type */
typedef int *MatrixGraph;

extern int *MatrixDijkstra();
extern Graph MatrixPrim();
extern Graph MatrixMaxFlow();
extern MatrixGraph ReadMatrix(), NewMatrix();

SHAR_EOF
fi
if test -f 'input.form'
then
	echo shar: "will not over-write existing file 'input.form'"
else
cat << \SHAR_EOF > 'input.form'
Disclaimer: the following description was obtained  by inspection of the
code and some simple tests.  It was not written by the implementor.  CCM

There will soon be available a program for translating from the DIMACS
standard format to this format.  Contributions are welcome. CCM

-------------------------------------------------------------------------
INPUT FORMAT FOR WMATCH:
-------------------------------------------------------------------------
   Graph I/O is performed by a generic graph library package, 
   so some of the fields are ignored by the "wmatch" code (but 
   you must include dummy fields in the input). 

   There are three types of lines: the first line, vertex lines, 
   and edge lines. The fields in each line type are as follows. 

   First line-> size edges U
      size: integer giving number of vertices
      edges: integer giving number of edges 
      U: character ``U'' or ``u'' specifying an undirected graph

   Vertex lines->  degree vlabel xcoord ycoord
      degree: edge degree of the vertex
      vlabel: vertex label (ignored--vertices are referred to by index)
      xcoord: integer x-coordinate location (ignored)
      ycoord: integer y-coordinate location (ignored) 

      *****Each vertex line is followed immediately by the lines 
      for all its adjacent edges (thus each edge appears twice, 
      once for each vertex).******

   Edge lines-> adjacent  weight
      adjacent: index (not vlabel) of the adjacent vertex
      weight: integer edge weight 
     





SHAR_EOF
fi
if test -f 'main.c'
then
	echo shar: "will not over-write existing file 'main.c'"
else
cat << \SHAR_EOF > 'main.c'
#include "graphtypes.h"

main(argc,argv)
int argc;
char *argv[];

{
	Graph graph;
	int *Mate;
	int i,size;

	if (argc < 2){
		printf("Usage: wmatch datafile\n");
		exit(1);
	}
	graph = ReadGraph(&size,argv[1]);
	Mate = Weighted_Match(graph,1);

	for (i=1; i<=size; i++)
		printf("%d %d\n",i,Mate[i]);
}


SHAR_EOF
fi
if test -f 'makefile'
then
	echo shar: "will not over-write existing file 'makefile'"
else
cat << \SHAR_EOF > 'makefile'
WMATCH = wmatch.c pairs.c pointer.c term.c unpairs.c readgraph.c

wmatch: main.o wmatch.o glib.o
	cc -o wmatch main.o wmatch.o glib.o -lm

$(WMATCH): match.defs

wmatch.o: $(WMATCH)
	cc -c wmatch.c -lm

SHAR_EOF
fi
if test -f 'match.defs'
then
	echo shar: "will not over-write existing file 'match.defs'"
else
cat << \SHAR_EOF > 'match.defs'
#define	MAXWT  1000000

#define NULL 0


/* the number of the blossom entered by edge e */
#define BEND(e) (BASE[END[e]])

/* the blossom matched with v's blossom */
#define BMATE(v) (BASE[END[MATE[v]]])

/* the blossom entered by the edge that links v's blossom */
#define BLINK(v) (BASE[END[LINK[v]]])

/* the edge e with it's direction reversed */
#define OPPEDGE(e) (((e - U) % 2 == 0) ? (e - 1) : (e + 1))

/* the slack of edge e */
#define SLACK(e) (Y[END[e]] + Y[END[OPPEDGE(e)]] - WEIGHT[e])


/* Global variables */
static int *A,*END,*WEIGHT,*NEXTPAIR;
static int *MATE,*LINK,*BASE,*NEXTVTX,*LASTVTX,*Y,*NEXT_D,*NEXTEDGE;

static int LAST_D, DELTA;

static int LASTEDGE[3];

static int DUMMYVERTEX, DUMMYEDGE;
static int U, V;

static int newbase, oldbase, nextbase, stopscan, pairpoint;
static int neighbor, nextpoint, newlast;
static int newmate, oldmate, oldfirst, firstmate, secondmate;
static int f, nextedge, nexte, nextu;

static int v,i,e;


SHAR_EOF
fi
if test -f 'output.form'
then
	echo shar: "will not over-write existing file 'output.form'"
else
cat << \SHAR_EOF > 'output.form'
Disclaimer: the following description was obtained by inspection of the
code and some simple tests.  It was not written by the implementor.  CCM

There will soon be available a program for translating from this output
format to the DIMACS standard format.  Contributions are welcome.  CCM
----------------------------------------------------------------------
OUTPUT FORMAT FOR WMATCH
----------------------------------------------------------------------

The i-th line:  Contains the i-th vertex and its mate.
				If the first entry is 0, the i-th vertex is unmatched.
 
  For example:
            1 3
            2 4 
            3 1
            4 2
            5 6
            6 5



SHAR_EOF
fi
if test -f 'pairs.c'
then
	echo shar: "will not over-write existing file 'pairs.c'"
else
cat << \SHAR_EOF > 'pairs.c'
/* Process an edge linking two linked vertices */
/* Note: global variable v set to the base of one end of the linking edge */

PAIR (outcome)
int *outcome;

{   int u, w, temp;

#ifdef DEBUG
    printf("Pair v=%d\n",v);
#endif

    e = NEXTEDGE[v];
    while (SLACK(e) != 2*DELTA)
	e = NEXTPAIR[e];
    w = BEND (e);
    LINK[BMATE (w)] = -e;
    u = BMATE (v);
    while (LINK[u] != -e) {
	LINK[u] = -e;
	if (MATE[w] != DUMMYEDGE) {
	    temp = v;
	    v = w;
	    w = temp; }
	v = BLINK (v);
	u = BMATE (v);
	}
    if (u == DUMMYVERTEX && v != w) {
	*outcome = 1;
	return;
	}
    newlast = v;
    newbase = v;
    oldfirst = NEXTVTX[v];
    LINK_PATH (e);
    LINK_PATH (OPPEDGE (e));
    NEXTVTX[newlast] = oldfirst;
    if (LASTVTX[newbase] == newbase)
	LASTVTX[newbase] = newlast;
    NEXTPAIR[DUMMYEDGE] = DUMMYEDGE;
    MERGE_PAIRS (newbase);
    i = NEXTVTX[newbase];
    do {
	MERGE_PAIRS (i);
	i = NEXTVTX[LASTVTX[i]];
	SCAN (i, 2*DELTA - SLACK(MATE[i]));
	i = NEXTVTX[LASTVTX[i]];
    } while (i != oldfirst);
    *outcome = 0;
    return;
}


/* merges a subblossom's pair list into a new blossom's pair list */
/* v is the base of the previously unlinked subblossom */
/* Note: global variable newbase set to the base of the new blossom */
/* 	called with NEXTPAIR[DUMMYEDGE] pointing to the first edge */
/*		on newbase's pair list */

MERGE_PAIRS (v)
int v;

{
#ifdef DEBUG
    printf("Merge Pairs v=%d\n",v);
#endif

    NEXT_D[v] = LAST_D;
    pairpoint = DUMMYEDGE;
    f = NEXTEDGE[v];
    while (f != DUMMYEDGE) {
	e = f;
	neighbor = END[e];
	f = NEXTPAIR[f];
	if (BASE[neighbor] != newbase)
	    INSERT_PAIR();
	}
}


/* links the unlinked vertices in the path P(END[e],newbase) */
/* Note: global variable newbase is set to the base vertex of the new blossom */
/*		newlast is set to the last vertex in newbase's current blossom*/

LINK_PATH (e)
int e;

{   int u;

#ifdef DEBUG
    printf("Link Path e=%d-%d\n", END[OPPEDGE(e)], END[e]);
#endif

    v = BEND (e);
    while (v != newbase) {
	u = BMATE (v);
	LINK[u] = OPPEDGE (e);
	NEXTVTX[newlast] = v;
	NEXTVTX[LASTVTX[v]] = u;
	newlast = LASTVTX[u];
	i = v;
	BASE[i] = newbase;
	i = NEXTVTX[i];
	while (i != DUMMYVERTEX) {
	    BASE[i] = newbase;
	    i = NEXTVTX[i];
	    }
	e = LINK[v];
	v = BEND (e);
	}
}


/* Update a blossom's pair list. */
/* Note: called with global variable e set to the edge to be inserted. */
/*			neighbor set to the vertex at the end of e */
/*			pairpoint set to the next pair on the pair list */

INSERT_PAIR ()

{   int del_e;

#ifdef DEBUG
    printf("Insert Pair e=%d-%d\n",END[OPPEDGE(e)],END[e]);
#endif

    del_e = SLACK(e)/2;
    nextpoint = NEXTPAIR[pairpoint];

    while (END[nextpoint] < neighbor) {
	pairpoint = nextpoint;
	nextpoint = NEXTPAIR[nextpoint];
	}
    if (END[nextpoint] == neighbor) {
	if (del_e >= SLACK (nextpoint)/2)
	    return;
	nextpoint = NEXTPAIR[nextpoint];
	}
    NEXTPAIR[pairpoint] = e;
    pairpoint = e;
    NEXTPAIR[e] = nextpoint;
    if (NEXT_D[newbase] > del_e)
	NEXT_D[newbase] = del_e;
}

SHAR_EOF
fi
if test -f 'pointer.c'
then
	echo shar: "will not over-write existing file 'pointer.c'"
else
cat << \SHAR_EOF > 'pointer.c'
/* Assign a pointer link to a vertex.  Edge e joins a vertex in blossom */
/* u to a linked vertex. */

POINTER (u,v,e)
int u,v,e;

{   int i, del;

#ifdef DEBUG
    printf("Pointer u,v,e=%d %d %d-%d\n",u,v,END[OPPEDGE(e)],END[e]);
#endif

    LINK[u] = -DUMMYEDGE;
    NEXTVTX[LASTVTX[u]] = DUMMYVERTEX;
    NEXTVTX[LASTVTX[v]] = DUMMYVERTEX;
    
    if (LASTVTX[u] != u) {
	i = MATE[NEXTVTX[u]];
	del = -SLACK(i) / 2;
	}
    else del = LAST_D;

    i = u;
    while (i != DUMMYVERTEX) {
	Y[i] += del;
	NEXT_D[i] += del;
	i = NEXTVTX[i];
	}
    if (LINK[v] < 0) {
	LINK[v] = e;
	NEXTPAIR[DUMMYEDGE] = DUMMYEDGE;
	SCAN (v, DELTA);
	return;
	}
    else {
	LINK[v] = e;
	return;
	}
}


/* Scan each vertex in the blossom whose base is x */

SCAN (x, del)
int x, del;

{   int u, del_e;

#ifdef DEBUG
    printf("Scan del=%d x=%d\n",del,x);
#endif

    newbase = BASE[x];
    stopscan = NEXTVTX[LASTVTX[x]];
    while (x != stopscan) {
	Y[x] += del;
	NEXT_D[x] = LAST_D;
	pairpoint = DUMMYEDGE;
	e = A[x];
	while (e != 0) {
	    neighbor = END[e];
	    u = BASE[neighbor];
	    if (LINK[u] < 0) {
		if (LINK[BMATE (u)] < 0 || LASTVTX[u] != u) {
		    del_e = SLACK (e);
		    if (NEXT_D[neighbor] > del_e) {
			NEXT_D[neighbor] = del_e;
			NEXTEDGE[neighbor] = e;
			}
		    }
		}
	    else if (u != newbase) {
		INSERT_PAIR();
		}
	    e = A[e];
	    }
	x = NEXTVTX[x];
	}
    NEXTEDGE[newbase] = NEXTPAIR[DUMMYEDGE];
}


SHAR_EOF
fi
if test -f 'readgraph.c'
then
	echo shar: "will not over-write existing file 'readgraph.c'"
else
cat << \SHAR_EOF > 'readgraph.c'
/* set up data structures for weighted match */

/* to add a new type, add new case in SetUp() and a Set_X() routine */

SetUp (gptr,type)
int gptr,type;

{   int i,allocsize;
    Graph g;
    EuclidGraph xy;
    MatrixGraph matg;

    if (type==1) {
	g = (Graph) gptr;
	U = Degree(g,0);
	V = NumEdges(g);
	}
    else if (type==2) {
	xy = (EuclidGraph) gptr;
	U = xy[0][0];
	V = U*(U-1)/2;
	}
    else if (type==3) {
	matg = (MatrixGraph) gptr;
	U = matg[0];
	V = U*(U-1)/2;
	}

    allocsize = (U+2*V+2)*sizeof(int);
    A      = (int *) malloc(allocsize);
    END    = (int *) malloc(allocsize);
    WEIGHT = (int *) malloc(allocsize);
    for (i=0; i<U+2*V+2; i++)
	A[i]=END[i]=WEIGHT[i]=0;

    if (type == 1) SetStandard(g);
    else if (type == 2) SetEuclid(xy);
    else if (type == 3) SetMatrix(matg);
}


/* set up from Type 1 graph. */

SetStandard(graph)
Graph graph;
{   int elabel, adj_node, i, j;
    int u, v, currentedge;
    Edge edge;

    currentedge = U+2;
    for (i=1; i<=U; ++i) {
	edge = FirstEdge(graph,i);
	for (j = 1; j <= Degree(graph,i); ++j) {
	    adj_node = EndPoint(edge);
	    if (i < adj_node) {
		elabel = ELabel(edge)*2;
		WEIGHT[currentedge-1] = WEIGHT[currentedge] = 2*elabel;
		END[currentedge-1] = i;
		END[currentedge] = adj_node;
		if (A[i] == 0)
		    A[i] = currentedge;
		else {
		    u = i;
		    v = A[i];
		    while (v != 0) {
			if (END[v] > adj_node)
			    break;
			u = v;
			v = A[v];
			}
		    A[u] = currentedge;
		    A[currentedge] = v;
		    }
		u = adj_node;
		v = A[u];
		while (v != 0) {
		    u = v;
		    v = A[v];
		    }
		A[u] = currentedge - 1;
		currentedge += 2;
		}
	    edge = NextEdge(edge);
	    }
	}
}

/* set up from Euclidean graph */

SetEuclid(graph)
EuclidGraph graph;
{   int i,j,currentedge;

    currentedge = U+2;

    for (i=U; i>=1; --i) 
	for (j = i-1; j >= 1; --j) {
	    WEIGHT[currentedge-1] = WEIGHT[currentedge]
		    = 2*eucdist2(graph,i,j);
	    END[currentedge-1] = i;
	    END[currentedge] = j;
	    A[currentedge] = A[i];
	    A[i] = currentedge;
	    A[currentedge-1] = A[j];
	    A[j] = currentedge-1;
	    currentedge += 2;
	    }
}

SetMatrix(graph)
MatrixGraph graph;
{   int i,j,currentedge;

    currentedge = U+2;

    for (i=U; i>=1; --i) 
	for (j = i-1; j >= 1; --j) {
	    WEIGHT[currentedge-1] = WEIGHT[currentedge]
		    = 2*graph[j*U+i];
	    END[currentedge-1] = i;
	    END[currentedge] = j;
	    A[currentedge] = A[i];
	    A[i] = currentedge;
	    A[currentedge-1] = A[j];
	    A[j] = currentedge-1;
	    currentedge += 2;
	    }
}

SHAR_EOF
fi
if test -f 'term.c'
then
	echo shar: "will not over-write existing file 'term.c'"
else
cat << \SHAR_EOF > 'term.c'
/* updates numerical bounds for linking paths. */
/* called with LAST_D set to the bound on DELTA for the next search */

SET_BOUNDS ()
 
{   int del;

    for (v=1; v <= U; ++v) {
	if (LINK[v] < 0 || BASE[v] != v) {
	    NEXT_D[v] = LAST_D;
	    continue;
	    }
	LINK[v] = -LINK[v];
	i = v;
	while (i != DUMMYVERTEX) {
	    Y[i] -= DELTA;
	    i = NEXTVTX[i];
	    }
	f = MATE[v];
	if (f != DUMMYEDGE) {
	    i = BEND(f);
	    del = SLACK(f);
	    while (i != DUMMYVERTEX) {
		Y[i] -= del;
		i = NEXTVTX[i];
		}
	    }
	NEXT_D[v] = LAST_D;
	}
}


/* undoes all blossoms to get the final matching */

UNPAIR_ALL ()

{   int u;

    for (v=1; v <= U; ++v) {
	if (BASE[v] != v || LASTVTX[v] == v)
	    continue;
	nextu = v;
	NEXTVTX[LASTVTX[nextu]] = DUMMYVERTEX;
	while (1) {
	    u = nextu;
	    nextu = NEXTVTX[nextu];
	    UNLINK (u);
	    if (LASTVTX[u] != u) {
		f = (LASTEDGE[2] == OPPEDGE(e)) ? LASTEDGE[1] : LASTEDGE[2];
		NEXTVTX[LASTVTX[BEND(f)]] = u;
		}
	    newbase = BMATE (BMATE(u));
	    if (newbase != DUMMYVERTEX && newbase != u) {
		LINK[u] = -DUMMYEDGE;
		REMATCH (newbase, MATE[u]);
		}
	    while (LASTVTX[nextu] == nextu && nextu != DUMMYVERTEX)
		    nextu = NEXTVTX[nextu];
	    if (LASTVTX[nextu] == nextu && nextu == DUMMYVERTEX)
		break;
	    }
	}
}


SHAR_EOF
fi
if test -f 'test.in'
then
	echo shar: "will not over-write existing file 'test.in'"
else
cat << \SHAR_EOF > 'test.in'
6 8 U
2 3 0 0 
2 6
3 8
3 3 0 0 
1 6 
5 3
4 6
3 3 0 0 
1 8
4 3
5 3
3 3 0 0 
2 6
3 3
6 8
3 3 0 0 
3 3
2 3
6 6
2 3 0 0 
4 8
5 6

SHAR_EOF
fi
if test -f 'unpairs.c'
then
	echo shar: "will not over-write existing file 'unpairs.c'"
else
cat << \SHAR_EOF > 'unpairs.c'
/* Expands a blossom.  Fixes up LINK and MATE. */

UNPAIR (oldbase, oldmate)
int oldbase, oldmate;

{   int e, newbase, u;

#ifdef DEBUG
    printf("Unpair oldbase, oldmate=%d %d\n",oldbase, oldmate);
#endif

    UNLINK (oldbase);
    newbase = BMATE (oldmate);
    if (newbase != oldbase) {
	LINK [oldbase] = -DUMMYEDGE;
	REMATCH (newbase, MATE[oldbase]);
	if (f == LASTEDGE[1])
	    LINK[secondmate] = -LASTEDGE[2];
	else LINK[secondmate] = -LASTEDGE[1];
	}
    e = LINK[oldmate];
    u = BEND (OPPEDGE (e));
    if (u == newbase) {
	POINTER (newbase, oldmate, e);
	return;
	}
    LINK[BMATE (u)] = -e;
    do {
	e = -LINK[u];
	v = BMATE (u);
	POINTER (u, v, -LINK[v]);
	u = BEND (e);
    } while (u != newbase);
    e = OPPEDGE (e);
    POINTER (newbase, oldmate, e);
}


/* changes the matching along an alternating path */
/* firstmate is the first base vertex on the path */
/* edge e is the new matched edge for firstmate   */

REMATCH (firstmate, e)
int firstmate, e;
 
{
#ifdef DEBUG
     printf("Rematch firstmate=%d e=%d-%d\n",firstmate, END[OPPEDGE(e)], END[e]);
#endif

    MATE[firstmate] = e;
    nexte = -LINK[firstmate];
    while (nexte != DUMMYEDGE) {
	e = nexte;
	f = OPPEDGE (e);
	firstmate = BEND (e);
	secondmate = BEND (f);
	nexte = -LINK[firstmate];
	LINK[firstmate] = -MATE[secondmate];
	LINK[secondmate] = -MATE[firstmate];
	MATE[firstmate] = f;
	MATE[secondmate] = e;
	}
}


/* unlinks subblossoms in a blossom.  oldbase is the base of the blossom to */
/* be unlinked. */

UNLINK (oldbase)
int oldbase;

{   int k, j=1;

#ifdef DEBUG
    printf("Unlink oldbase=%d\n",oldbase);
#endif

    i = NEXTVTX[oldbase];
    newbase = NEXTVTX[oldbase];
    nextbase = NEXTVTX[LASTVTX[newbase]];
    e = LINK[nextbase];
UL2:
    do {
	nextedge = OPPEDGE (LINK[newbase]);
	for (k=1; k <= 2; ++k) {
	    LINK[newbase] = -LINK[newbase];
	    BASE[i] = newbase;
	    i = NEXTVTX[i];
	    while (i != nextbase) {
		BASE[i] = newbase;
		i = NEXTVTX[i];
		} 
	    newbase = nextbase;
	    nextbase = NEXTVTX[LASTVTX[newbase]];
	    }
	} while (LINK[nextbase] == nextedge);
    if (j==1) {
	LASTEDGE[1] = nextedge;
	j++;
	nextedge = OPPEDGE (e);
	if (LINK[nextbase] == nextedge) {
	    goto UL2;
	    }
	}
    LASTEDGE[2] = nextedge;

    if (BASE[LASTVTX[oldbase]] == oldbase) 
	NEXTVTX[oldbase] = newbase;
    else {
	NEXTVTX[oldbase] = DUMMYVERTEX;
	LASTVTX[oldbase] = oldbase;
	}
}


SHAR_EOF
fi
if test -f 'wmatch.c'
then
	echo shar: "will not over-write existing file 'wmatch.c'"
else
cat << \SHAR_EOF > 'wmatch.c'
/* N-cubed weighted matching */
/* Implementation of H. Gabow's Ph.D. thesis, Stanford Univ. 1973 */
/* Written by Edward Rothberg  7/85 */
/* For complete details, please refer to the original paper */

/* Send either a Euclidean graph or an adjacency list graph. */
/* Returns an array, the ith entry being the mate of vertex 'i'. */
/* A zero entry indicates an unmatched vertex. */

/* To add new type, see readgraph.c */

#include "match.defs"
#include "graphtypes.h"
#include "pairs.c"
#include "pointer.c"
#include "readgraph.c"
#include "term.c"
#include "unpairs.c"

int *Weighted_Match (gptr,type,maximize)
int gptr,type,maximize;

{   int g, j, w, outcome, loop=1;

    /* set up internal data structure */
    SetUp(gptr,type);
    Initialize(maximize);

    for(;;) {
	/* printf("Augment #%d\n",loop++); */
	DELTA = 0;
	for (v=1; v<=U; ++v)
	    if (MATE[v] == DUMMYEDGE)
		POINTER (DUMMYVERTEX, v, DUMMYEDGE);
	for(;;) {
	    i = 1;
	    for (j=2; j<=U; ++j)
		if (NEXT_D[i] > NEXT_D[j])
		    i = j;
	    DELTA = NEXT_D[i];
	    if (DELTA == LAST_D)
		goto done;
	    v = BASE[i];
	    if (LINK[v] >= 0) {
		PAIR (&outcome);
		if (outcome == 1)
		    break;
		}
	    else {
		w = BMATE (v);
		if (LINK[w] < 0) {
		    POINTER (v, w, OPPEDGE(NEXTEDGE[i]));
		    }
		else UNPAIR (v, w);
	        }
	    }

	LAST_D -=DELTA;
	SET_BOUNDS();
	g = OPPEDGE(e);
	REMATCH (BEND(e), g);
	REMATCH (BEND(g), e);
	}
    
done:
    SET_BOUNDS();
    UNPAIR_ALL();
    for (i=1; i<=U;++i) {
	MATE[i] = END[MATE[i]];
	if (MATE[i]==DUMMYVERTEX)
	    MATE[i]=0;
	}

    FreeUp();
    return(MATE);
}


Initialize(maximize)

{   int i, allocsize, max_wt= -MAXWT, min_wt=MAXWT;

    DUMMYVERTEX = U+1;
    DUMMYEDGE = U+2*V+1;
    END[DUMMYEDGE] = DUMMYVERTEX;

    for (i=U+2; i<=U+2*V; i+=2) {
	if (WEIGHT[i] > max_wt)
	    max_wt = WEIGHT[i];
	if (WEIGHT[i] < min_wt)
	    min_wt = WEIGHT[i];
	}
    if (!maximize) {
	if (U%2!=0) {
	    printf("Must have an even number of vertices to do a\n");
	    printf("minimum complete matching.\n");
	    exit(0);
	    }
	max_wt += 2; /* Don't want all zero weight */
	for (i=U+1; i<=U+2*V; i++)
	    WEIGHT[i] = max_wt-WEIGHT[i];
	max_wt = max_wt-min_wt;
	}
    LAST_D = max_wt/2;

    allocsize = (U+2)*sizeof(int);
    MATE     = (int *) malloc(allocsize);
    LINK     = (int *) malloc(allocsize);
    BASE     = (int *) malloc(allocsize);
    NEXTVTX  = (int *) malloc(allocsize);
    LASTVTX  = (int *) malloc(allocsize);
    Y        = (int *) malloc(allocsize);
    NEXT_D   = (int *) malloc(allocsize);
    NEXTEDGE = (int *) malloc(allocsize);
    allocsize = (U+2*V+2)*sizeof(int);
    NEXTPAIR = (int *) malloc(allocsize);

    for (i = 1; i <= U+1; ++i) {
	MATE[i] = DUMMYEDGE;
	NEXTEDGE[i] = DUMMYEDGE;
	NEXTVTX[i] = 0;
	LINK[i] = -DUMMYEDGE;
	BASE[i] = i;
	LASTVTX[i] = i;
	Y[i] = LAST_D;
	NEXT_D[i] = LAST_D;
	}
}

FreeUp()
{
    free(LINK);
    free(BASE);
    free(NEXTVTX);
    free(LASTVTX);
    free(Y);
    free(NEXT_D);
    free(NEXTEDGE);
    free(NEXTPAIR);
    free(A);
    free(END);
    free(WEIGHT);
}

SHAR_EOF
fi
exit 0
#   End of shell archive
